package ru.eas.fibonachi;

import java.util.Scanner;

public class FibonachiModule {
    public static void main(String[] args)
    {
//        String testString = "18825555099925889 60414";
//        Scanner scanner = new Scanner(testString);

        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        int m = scanner.nextInt();
        System.out.println(fibMod(n, m));
    }

    private static long fibMod(long n, int m) {
        long a11 = 1, a12 = 1, a21 = 1, a22 = 0;
        long r11 = 1, r12 = 0;
        long q11, q12, q21, q22;
        while (n > 0) {
            if ((n&1) == 1) {
                q11 = (r11 * a11 + r12 * a21) % m;
                q12 = (r11 * a12 + r12 * a22) % m;
                r11 = q11;
                r12 = q12;
            }
            q11 = (a11 * a11 + a12 * a21) % m;
            q12 = (a11 * a12 + a12 * a22) % m;
            q21 = (a21 * a11 + a22 * a21) % m;
            q22 = (a21 * a12 + a22 * a22) % m;
            a11 = q11;
            a12 = q12;
            a21 = q21;
            a22 = q22;

            n >>= 1;
        }
        return r12;
    }
}
